The present invention relates generally to broadcast encryption methods, and more particularly to a method for reducing the number of encryption keys and thus the number of transmissions required to transmit an encrypted program to its intended recipients.
Conventional encryption methods are widely used today to limit the number of viewers who can view certain broadcast programs, such as pay-per-view programs. Broadcasters use such methods to securely transmit program content over cable or satellite television systems, or over the Internet, to prevent viewers who have not paid for the program from either intentionally or unintentionally being able to view the program. Such programs are typically broadcast to a population of viewers from a head-end transmitter which securely encrypts the programs using establishment keys selected by the head-end transmitter so that only viewers who paid for the program can view the program. In order to decrypt the program, these intended viewers are provided with set-top terminals (STTs) containing the establishment keys.
The STTs typically contain a chip having a secure memory capable of storing approximately 100 establishment keys. This secure memory is generally non-volatile, and tamper-resistant in order to decrease the likelihood of piracy. It is also preferably writeable so that it can be reprogrammed with different establishment keys for other programs, such as a future pay-per-view event.
Each viewer typically stores a plurality of establishment keys in their STT, some of which may be shared by other viewers. Consequently, when the head-end transmitter transmits a program encrypted with certain keys to a particular group of viewers, viewers who are not in this group but who possess these common keys in their STT will also be able to view the program.
Before it can transmit an encrypted program to any of its viewers, a broadcast system operator must first allocate establishment keys which are stored in the STT provided to each one of its subscribers. At present there are two conventional methods used for allocating establishment keys so that only certain intended viewers can decrypt a program, either: (a) each different potential viewer is allocated a unique establishment key for decrypting a program; or (b) viewers are allocated multiple common establishment keys which they share with other viewers, wherein a separate key is allocated for each possible combination of at least two viewers from all of the possible viewers and each viewer receives those keys for combinations of viewers which include them.
Programs are encrypted by the head-end transmitter with one key each time they are transmitted. Thus, if method (a) is used, the head-end transmitter will transmit a program as many times as there are members of an intended target group, with the program being encrypted with a different one of the unique establishment keys each transmission, thereby ensuring that each member of the target group receives the program. If method (b) is used, the head-end transmitter will transmit a program only once, since it can use a key that exactly corresponds to the target group.
Alternatively, the head-end transmitter need not re-encrypt a program multiple times in order to broadcast the program to its intended recipients. Instead, the head-end can encrypt the program once with a program entitlement which it in turn encrypts as many times as the number of keys it has to use to ensure that each member of a target group of viewers receives the program. The program entitlement is attached as a header at the beginning of the transmission of a program. Since less bandwidth is required to transmit a program entitlement than is required to transmit a program, this method of transmitting encrypted programming results in shorter transmission lengths, especially when method (a) is used. When a program entitlement is used to encrypt a program, the establishment keys in the STT decrypt the entitlement in order for the program to be viewed.
The conventional encryption methods described above suffer from significant drawbacks. Method (a) typically requires repeated encrypted transmissions of a program, wherein with each transmission the program is encrypted with a different key possessed by at least one member one of the target set of viewers to ensure that all such intended viewers receive the program. Consequently, during such repeated transmissions a broadcaster is unable to use the broadcast bandwidth to broadcast other revenue generating programming. Method (b) typically requires users to store a prohibitively large number of establishment keys in their STT in order to be able to decrypt programs.
A method for encrypting programming, wherein by allowing a controlled number of unintended recipients to receive a broadcast of a program, a smaller set of encryption keys can be selected for encrypting the program, thereby requiring fewer transmissions to broadcast the program to each member of a target set of intended recipients who paid to receive the program than is required using conventional encryption methods which only allow programs to be viewed by its intended recipients. The method operates by determining an acceptable f-ratio of a total number of viewers of the broadcast program to a number of intended viewers in an identified target set who paid to receive the program. The target set of viewers is included in the total number of viewers. In one preferred embodiment, the f-ratio is selected so that the total number of viewers is between one to two times the number of viewers in the target set, for any possible target set.
The broadcast system operator constructs an f-redundant establishment key allocation set from which the establishment keys for encrypting the program are selected. An approximation algorithm is then used to select a key cover set of establishment keys from the establishment key allocation set, wherein the keys in the cover set are used to encrypt the program. The key cover set uses fewer establishment keys to encrypt a program than conventional methods which only allow paying viewers to receive a program, thereby requiring fewer transmissions to broadcast a program to all of its intended paying recipients and consequently providing a more efficient and less expensive method of broadcasting encrypted programming.